package com.LC._198;

// 状态 State
// 灵感，创造力，存储小规模问题的结果
// 方程 Function
// 状态之间的联系，怎么通过小的状态，来算大的状态
// 初始化 Intialization
// 最极限的小状态是什么, 起点
// 答案 Answer
// 最大的那个状态是什么，终点
// class Solution {
//     public int rob(int[] nums) {
//         int[][] dp = new int[nums.length][2];
//         //dp init
//         dp[0][0]=0;
//         dp[0][1]=nums[0];
//         //dp[i]表示 第i个房子get到的钱
//         for(int i=1;i<nums.length;i++){
//             //0表示mei投 1表示偷
//             dp[i][0] = Math.max(dp[i-1][1] ,dp[i-1][0]);//保存两种状态发生后的结果
//             dp[i][1] = dp[i-1][0]+nums[i];
//         }
//         return Math.max(dp[nums.length-1][0],dp[nums.length-1][1]);
//     }
// }

class Solution {
    public int rob(int[] nums) {
        int[][] dp = new int[nums.length][2];
        dp[0][0]=0;
        dp[0][1]=nums[0];
        for(int i=1;i<nums.length;i++){
            //不确定状态 =>无法确下一步
            dp[i][0]=Math.max(dp[i-1][1],dp[i-1][0]);
            //可以确定下一步所以只要在当前把dp[i]最大化即可
            dp[i][1]=dp[i-1][0]+nums[i];
        }
        return Math.max(dp[nums.length-1][0],dp[nums.length-1][1]);
    }
}